package j2024.j202412;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class j1230 {
    /**
     * 437. 路径总和 III
     * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
     *
     * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     */
    Map<Long,Integer> map = new HashMap<>();
    int ret,t;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        t = targetSum;
        map.put(0L, 1);
        dfs(root,root.val);
        return ret;
    }
    private void dfs(TreeNode root, long v) {
        if(map.containsKey(v-t)){
            ret+=map.get(v-t);
        }
        map.put(v,map.getOrDefault(v,0)+1);
        if(root.left!=null){
            dfs(root.left,v+root.left.val);
        }
        if(root.right!=null){
            dfs(root.right,v+root.right.val);
        }
        map.put(v,map.getOrDefault(v,0)-1);
    }


    /**
     * 236. 二叉树的最近公共祖先
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     *
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
     * 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        Stack<TreeNode> sp = new Stack<>();
        Stack<TreeNode> sq = new Stack<>();
        ispath(root,sp,p);
        ispath(root,sq,q);
        int ps = sp.size(),qs = sq.size();
        if(ps>qs){
            int s = ps-qs;
            while(s>0){
                sp.pop();
                s--;
            }
        }else{
            int s = qs-ps;
            while(s>0){
                sq.pop();
                s--;
            }
        }
        while(!sq.isEmpty() && !sp.isEmpty()){
            TreeNode nodep = sp.pop();
            TreeNode nodeq = sq.pop();
            if(nodeq == nodep){
                return nodep;
            }
        }
        return null;
    }
    private boolean ispath(TreeNode root,Stack<TreeNode> s,TreeNode cur){
        if(root == null) return false;
        s.push(root);
        if(cur==root) return true;
        boolean left = ispath(root.left,s,cur);
        if(left) return true;
        boolean right = ispath(root.right,s,cur);
        if(right) return true;
        s.pop();
        return false;
    }
}
